#include "DoubleLinkList.h"
#include <stdio.h>
#include <stdlib.h>

DLNode* CreateNode(ElementType element)
{  
    DLNode *newNode = (DLNode*)malloc(sizeof(DLNode));
    if(newNode == NULL)
    {
        printf("create Node malloc error!\n");
        return NULL;
    }
    newNode->data = element;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

void InitDLlist(DLlist * list)
{
    list->head = list->tail = CreateNode(NULL);
    list->len = 0;    
}



void InsertDLlistTial(DLlist * list, ElementType element)
{
    DLNode *newNode = CreateNode(element);
    if(newNode == NULL)
        return;
    list->tail->next = newNode;
    newNode->prev = list->tail;
    list->tail = newNode;
    list->len++;
}

void InsertDLlistHead(DLlist * list, ElementType element)
{
    if(list->len == 0)
    {
        InsertDLlistTial(list,element);
    }
    else
    {
        DLNode *newNode = CreateNode(element);
        if(newNode == NULL)
            return;
        newNode->next = list->head->next;
        newNode->prev = list->head;
        list->head->next->prev = newNode;
        list->head->next = newNode;
        list->len++;
    }
}

void RemoveByIndex(DLlist * list, int index,void (*freePtr)(ElementType))
{
    if(index < 0 || index >= list->len)
    {
        printf("删除的位置非法:%d len : %d\n",index,list->len);
        return;
    }

    if(index == list->len-1)
    {
        DLNode *Prev = list->tail->prev;
        Prev->next = NULL;
        if(freePtr != NULL)
        {
            freePtr(list->tail->data);
        }
        free(list->tail);
        list->tail = Prev;
    }
    else
    {
        DLNode *travelPoint = list->head;
        for(int i = 0; i < index; i++)
        {
            travelPoint = travelPoint->next;
        }
        DLNode *freeNode =  travelPoint->next;
        travelPoint->next = freeNode->next;
        freeNode->next->prev = travelPoint;
        if(freePtr != NULL)
        {
            freePtr(freeNode->data);
        }
        free(freeNode); 
    }
    list->len--;
}

void RemoveByElement(DLlist * list, ElementType element, bool(* OperPtr)(ElementType,ElementType), void(* freePtr)(ElementType))
{
    DLNode *travelPoint = list->head;
    int index = 0;
    while(travelPoint->next != NULL)
    {
        if(OperPtr(travelPoint->next->data,element) == true)
        {
            RemoveByIndex(list,index,freePtr);
        }
        else
        {
            index++;
            travelPoint = travelPoint->next;
        }
    }
}

ElementType * FindByIndex(DLlist * list, int index)
{
    if(index < 0 || index >= list->len)
    {
        printf("非法的查找位置\n");
        return NULL;
    }

    DLNode *travelPoint = list->head->next;
    for(int i = 0; i < index;i++)
    {
        travelPoint = travelPoint->next;
    }
    return &travelPoint->data;
}

DLlist FindByElement(DLlist * list, ElementType element, bool(* OperPtr)(ElementType,ElementType))
{
    INITDLLIST(result);

    DLNode *travelPoint = list->head;
    while(travelPoint->next != NULL)
    {
        if(OperPtr(travelPoint->next->data,element) == true)
        {
            InsertDLlistTial(&result,travelPoint->next->data);
        }
        travelPoint = travelPoint->next;
    }
    return result;
}

void TravelDLlist(DLlist * list, void(* funcPtr)(ElementType))
{
    if(funcPtr == NULL)
        return;

    DLNode *travelPoint = list->head->next;
    while(travelPoint != NULL)
    {
        funcPtr(travelPoint->data);
        travelPoint = travelPoint->next;
    }
}

void Swap(ElementType* value1,ElementType* value2)
{
    ElementType temp = *value1;
    *value1 = *value2;
    *value2 = temp;
}

void FastSort(DLNode *start, DLNode *end,bool (*funcPtr)(void *,void *))
{
    if(start == end)
    {
        return;
    }

    DLNode *p1 = start;
    DLNode *p2 = start->next;

    while(p2 != end)
    {
        if(funcPtr(p2->data,start->data) == true)
        {
            p1 = p1->next;
            Swap(&p1->data,&p2->data);
        }
        p2 = p2->next;
    }
    Swap(&start->data,&p1->data);

    FastSort(start,p1,funcPtr);
    FastSort(p1->next,p2,funcPtr);
}

void DLlistSort(DLlist * list, bool (* funcPtr)(ElementType,ElementType))
{
    FastSort(list->head->next,NULL,funcPtr);
}

void ClearDLlist(DLlist * list, void(* clearPtr)(ElementType))
{
    while(list->head != NULL)
    {
        DLNode *next = list->head->next;
        if(list->head->data != NULL && clearPtr != NULL)
        {
            clearPtr(list->head->data);
        }
        free(list->head);
        list->head = next;
    }
    list->len = 0;
}

